#pragma once


template<typename E>
struct BiTNode
{
    E data;
    BiTNode *lchild,*rchild;
};

template<typename E>
using BiTree = BiTNode<E> *;


template<typename E,typename F>
void Preorder(BiTree<E> T,F visit)
{
    if(T){
        visit(T->data);
        Preorder(T->lchild,visit);
        Preorder(T->rchild,visit);
    }
}

template<typename E,typename F>
void Inorder(BiTree<E> T,F visit)
{
    if(T){
        
        Inorder(T->lchild,visit);
        visit(T->data);
        Inorder(T->rchild,visit);
    }
}




template<typename E,typename F>
void Postorder(BiTree<E> T,F visit)
{
    if(T){
        
        Postorder(T->lchild,visit);
        Postorder(T->rchild,visit);
        visit(T->data);
    }
}

//求二叉树节点
template<typename E>
int NodeCount(BiTree<E> T)
{
    if(T== nullptr)
        return 0;
    auto L=NodeCount(T->lchild);
    auto R=NodeCount(T->rchild);
    return L+R+1;

}
//秋叶子几点数
template<typename E>
int LeafCount(BiTree<E> T)
{
    if(T==nullptr)
        return 0;
    if(T->lchild==nullptr&&T->rchild==nullptr)
        return 1;
    auto L=LeafCount(T->lchild);
    auto R=LeafCount(T->rchild);
    return L+ R;
}

//求二叉树深度
template<typename E>
int Depth(BiTree<E> T)
{
    if(T==nullptr)
        return 0;
    auto L=Depth(T->lchild);
    auto R=Depth(T->rchild);
    return L>R ? L+1:R+1;
}

#include<iostream>
using std::cout;
using std::endl;

//打印二叉树
template<typename E>
void Print(BiTree<E> T,char prefix='$',int level=0)
{
    if(T){
        Print(T->rchild,'/',level+1);
        for(int i=0;i<level;++i) cout <<"  ";
        cout<<prefix<<' '<<T->data<<endl;
        Print(T->lchild,'\\',level+1);
    }
}
#include <iostream>
using std::cin;
using std::noskipws;

//建立二叉树
BiTree<char> CreateBinaryTree()
{
    char c;
    cin>>noskipws>>c;
    if(c==' ')return nullptr;
    auto T=new BiTNode<char>{c,nullptr,nullptr};
    T->lchild=CreateBinaryTree();
    T->rchild=CreateBinaryTree();
    return T;
}

//销毁
template<typename E>
void Destroy(BiTree<E> &T)
{
    if(T){
        Destroy(T->lchild);
        Destroy(T->rchild);
        delete T;
        T=nullptr;
    }
}

//二叉排序树
//二叉排序树查找算法
template<typename E>
BiTree<E> SearcharBST(BiTree<E> T,E e)
{
    if(!T|| T->data==e)
        return T;
    
    else if(e< T->data)
        return SearcharBST(T->lchild,e);
    else 
        return SearcharBST(T->rchild,e);
    
}

//二叉排序树找最小
template<typename E>
BiTree<E> FindMinBST(BiTree<E> T)
{
    if(T)
        while(T->lchild)
            T=T->lchild;
    return T;
}
//二叉排序树找最大
template<typename E>
BiTree<E> FindMaxBST(BiTree<E> T)
{
    if(T)
        while(T->rchild)
            T=T->rchild;
    return T;
}
template<typename E>
void InsertBST(BiTree<E> &T,E e)
{
    if(T==nullptr)
        T=new BiTNode<E>{e,nullptr,nullptr};
    else if (e<T->data)
        InsertBST(T->lchild,e);
    else if (e>T->data)
        InsertBST(T->rchild,e);
    else
        ;
}

//二叉排序树删除
template<typename E>
void DeleteBST(BiTree<E> &T,E e)
{
    if(T==nullptr) return;
    else if (e<T->data)
        DeleteBST(T->lchild,e);
    else if (e>T->data)
        DeleteBST(T->rchild,e);
    else{
        if(T->lchild && T->rchild)
        {
            T->data=FindMaxBST(T->lchild)->data;
        
            DeleteBST(T->lchild,T->data);
        }
        else{
            auto oldNode=T;
            T=T->lchild?T->lchild:T->rchild;
            delete oldNode;
        }

    }
}